package com.ting.test.algorithms.二叉树;

import java.util.*;

/**
 * 给定一棵二叉树的头节点head，和另外两个节点a和b。
 * 返回a和b的最低公共祖先
 * <p>
 * 可以创建一个map，把整棵树的父子关系记录起来，然后再将A的整个链路都存在一个set集合中，
 * 从b开始向上遍历节点，如果发现b的父节点在set集合中，则该节点就是他们的最低公共祖先
 */
public class 判断最低公共祖先1 {
    public static void main(String[] args) {
        TreeNode head = new TreeNode(2);
        TreeNode nodeA = new TreeNode(4);
        TreeNode nodeB = new TreeNode(2);
        TreeNode result = latestCommonParent(head, nodeA, nodeB);
        System.out.println(result);
    }

    private static TreeNode latestCommonParent(TreeNode head, TreeNode nodeA, TreeNode nodeB) {
        if (head == null || nodeA == null || nodeB == null) {
            return null;
        }
        // 利用层序遍历，将每个节点的对应关系存储在map
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(head);
        HashMap<TreeNode, TreeNode> map = new HashMap();
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            if (poll.left != null) {
                map.put(poll.left, poll);
                queue.add(poll.left);
            }
            if (poll.right != null) {
                map.put(poll.right, poll);
                queue.add(poll.right);
            }
        }

        Set<TreeNode> aset = new HashSet<>();

        // 将A的父节点包括A自己存储到一个set中
        TreeNode parent = nodeA;
        while (parent != null) {
            aset.add(parent);
            parent = map.get(parent);
        }

        // 从下往上依次遍历B的父节点，如果在set中存在，则该节点就是B和A的最低公共父节点
        TreeNode parentB = nodeB;
        while (parentB != null) {
            if (aset.contains(parentB)) {
                return parentB;
            }
        }
        return null;
    }

}
